package com.heima.algorithm.dynamicprogramming;

import java.util.ArrayList;
import java.util.List;

/**
 * 用动态规划实现BellmanFord算法
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/5 10:37
 */
public class BellmanFord {
    /*
        一、假如有图：
            v1 --- 7  --> v2 --- 9  --> v3 --- 14  --> v6
            v2 --- 15 --> v4
            v3 --- 11 --> v4 --- 2  --> v6
            v4 --- 6  --> v5
            v5
            v6 --- 9  --> v5

         二、原本bellmanFord算法思路：循环 总节点数 - 1 次，每次循环遍历所有顶点，遍历所有顶点时遍历该顶点的所有邻接边，更新邻接顶点的距离和prev

         三、动态规划思路：
         f(v) 用来表示从起点v0出发，到任意v这个顶点的最短距离

         初始：
         当v == v0时，f(v) = 0
         当v != v0时，f(v) = infinity(无穷大)

         之后：
         f(to) = min(f(to), f(from) + from.weight) // from和to是邻接关系，所有的from都要来一次

         例如上述例子：
         假如起点v1，终点v5
         f(v5) = min(infinity, f(v4) + 6) = 26
            f(v4) = min(infinity, f(v2) + 15) = 22
                f(v2) = min(infinity, f(v1) + 7) = 7
            f(v4) = min(22, f(v3) + 11) = 20
                f(v3) = min(infinity, f(v1) + 9) = 9
         f(v5) = min(26, f(v6) + 9) = 20
            f(v6) = min(infinity, f(v1) + 14) = 14
            f(v6) = min(14, f(v3) + 2) = 11

         v1  v2  v3  v4  v5  v6
         0   ∞   ∞   ∞   ∞   ∞
         0   7   9   20  20  11
         0   7   9   20  20  11
         0   7   9   20  20  11
         0   7   9   20  20  11
         0   7   9   20  20  11
     */
    List<Vertex> vertices;

    private static final int INFINITY = Integer.MAX_VALUE;

    BellmanFord() {
        vertices = new ArrayList<>();
    }

    static class Vertex {
        String name;
        List<Edge> edges;
        public Vertex(String name) {
            this.name = name;
            this.edges = new ArrayList<>();
        }
    }

    static class Edge {
        Vertex linked;
        int weight;
        public Edge(Vertex linked, int weight) {
            this.linked = linked;
            this.weight = weight;
        }
    }

    void bellmanFord(Vertex start) {
        // 动态规划核心
        int[] dp = new int[vertices.size()];
        int index = vertices.indexOf(start);
        for (int i = 0; i < dp.length; i++) {
            if (i == index){
                dp[i] = 0;
            }else {
                dp[i] = INFINITY;
            }
        }

        // 算法核心
        for (int i = 0; i < vertices.size() - 1; i++) {
            for (Vertex vertex : vertices) {
                for (Edge edge : vertex.edges) {
                    int vertexIndex = vertices.indexOf(vertex);
                    int linkedIndex = vertices.indexOf(edge.linked);
                    if (dp[vertexIndex] != INFINITY){
                        dp[linkedIndex] = Math.min(dp[linkedIndex], dp[vertexIndex] + edge.weight);
                    }
                }
            }
        }

        // 打印
        for (int i = 0; i < dp.length; i++) {
            System.out.println(vertices.get(i).name + " " + dp[i]);
        }
    }

    public static void main(String[] args) {
        BellmanFord bellmanFord = new BellmanFord();

        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges.add(new Edge(v2, 7));
        v1.edges.add(new Edge(v3, 9));
        v1.edges.add(new Edge(v6, 14));

        v2.edges.add(new Edge(v4, 15));

        v3.edges.add(new Edge(v4, 11));
        v3.edges.add(new Edge(v6, 2));

        v4.edges.add(new Edge(v5, 6));

        v6.edges.add(new Edge(v5, 9));

        bellmanFord.vertices.addAll(List.of(v1, v2, v3, v4, v5, v6));

        bellmanFord.bellmanFord(v1);
    }
}
